package _07_串;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/permutation-in-string/
 * @Author: haogege
 * @Date: 2021/9/21
 */
public class _567_字符串的排列 {

    // 滑动窗口优化版本，使用一个标记数组
    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        if (len1 > len2) {
            return false;
        }
        int[] ct1 = new int[26];
        for (int i = 0; i < len1; i++) {
            ct1[s1.charAt(i) - 'a']--;
            ct1[s2.charAt(i) - 'a']++;
        }
        // 当前滑动窗口的不同元素个数
        int diff = 0;
        for (int c : ct1) {
            if (c != 0) {
                diff++;
            }
        }
        if (diff == 0)  return true;
        for (int i = len1; i < len2; i++) {
            // 滑进来的元素
            int x = s2.charAt(i) - 'a';
            // 滑动出去的元素
            int y = s2.charAt(i - len1) - 'a';
            if (x == y) continue;
            if (ct1[x]++ == 0) {
                // 当前进来元素需要加一
                diff++;
            }
            if (ct1[x] == 0) {
                diff--;
            }
            if (ct1[y]-- == 0) {
                diff++;
            }
            if (ct1[y] == 0) {
                diff--;
            }
            if (diff == 0) return true;
        }
        return false;
    }

    // 滑动窗口: 如果需要比较字母排列是否相等，并且字母个数不是很多，可以使用数组，存入元素个数，然后比较数组是否相等即可
    public boolean checkInclusion1(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        if (len1 > len2) {
            return false;
        }
        int[] ct1 = new int[26];
        int[] ct2 = new int[26];
        for (int i = 0; i < len1; i++) {
            ct1[s1.charAt(i) - 'a']++;
            ct2[s2.charAt(i) - 'a']++;
        }
        // 如果当前相等者正确
        if (Arrays.equals(ct1, ct2)) {
            return true;
        }

        for (int i = len1; i < len2; i++) {
            ct2[s2.charAt(i - len1) - 'a']--;
            ct2[s2.charAt(i) - 'a']++;
            if (Arrays.equals(ct1, ct2)) {
                return true;
            }
        }
        return false;
    }

}
